# 390. 消除游戏
# https://leetcode-cn.com/problems/elimination-game/
# 列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
#
# 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
# 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
# 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
# 给你整数 n ，返回 arr 最后剩下的数字。
#
#  
#
# 示例 1：
#
# 输入：n = 9
# 输出：6
# 解释：
# arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# arr = [2, 4, 6, 8]
# arr = [2, 6]
# arr = [6]
# 示例 2：
#
# 输入：n = 1
# 输出：1
#
# 提示：
#
# 1 <= n <= 10^9
#
# 题解:
# - n很大, 如果通过制造集合来做的话很可能搞不定
# - 数组在消除元素时总是维持一个等差数列, 因此只要界定好每次消除的: 起始方向, 最大最小值, 公差即可

class Solution:
    def lastRemaining(self, n: int) -> int:
        left = -1
        min_value = 1
        max_value = n
        d = 1

        while min_value < max_value:
            pre_d = d
            d = d * 2

            # 计算下一个min_value和max_value
            if left < 0:
                min_value += pre_d
                max_value = (max_value - min_value) // d * d + min_value
            else:
                max_value -= pre_d
                min_value = max_value - (max_value - min_value) // d * d
            left *= -1
        return min_value


solution = Solution()
assert solution.lastRemaining(1) == 1
assert solution.lastRemaining(9) == 6

